package com.backpack;

/**
 * 两个字符串的删除操作
 * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 * 每步 可以删除任意一个字符串中的一个字符。
 *
 * 输入: word1 = "sea", word2 = "eat"
 * 输出: 2
 * 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
 */
public class DeleteOperationforTwoStrings0119_583 {
    public int minDistance(String word1, String word2) {
        //相当于 求最长公共子序列问题，返回 长度的差值即为所求步数
        //动态规划思路：
        //dp 含义：表示以[i-1]下标元素结尾的 word1子字符串 和以[j-1]下标元素结尾的 word2子字符串 含有最长公共子序列的长度
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        //返回值：word1.length() + word2.length() - 2*（dp的最大值）;
        //        int max = 0;
        //初始化：0;

        //
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
//                max = Math.max(max,dp[i][j]);
            }
        }
        return word1.length() + word2.length() - 2 * (dp[word1.length()][word2.length()]);
    }
}
